class Solution:
    """
     方法： 使用动态规划求解字符串的编辑距离
            dp[j]表示word1的前i个字符转换到word2的前j个字符所需的最小操作数
            当字符相同时，dp[j] = pre (pre为dp[i-1][j-1])
            当字符不同时，dp[j] = min(dp[j-1], dp[j], pre) + 1
            分别对应插入、删除、替换操作
     
     Args:
         word1: str - 源字符串
         word2: str - 目标字符串
     
     Returns:
         int: 将word1转换为word2所需的最小操作数
     
     Time: O(m*n) - m和n分别为两个字符串的长度，需要填充m*n的dp表
     
     Space: O(n) - 使用一维数组优化空间，n为目标字符串长度
     """
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
    
        # 使用一维数组优化空间复杂度
        dp = [0] * (n + 1)
        
        # 初始化第一行（空字符串转换为word2前j个字符的编辑距离）
        for j in range(n + 1):
            dp[j] = j
        
        for i in range(1, m + 1):
            # 保存左上角的值（相当于dp[i-1][j-1]）
            pre = dp[0]
            # 初始化当前行的第一个值（相当于dp[i][0]）
            dp[0] = i
            
            for j in range(1, n + 1):
                # 保存当前值，作为下一次迭代的pre
                temp = dp[j]
                
                if word1[i-1] == word2[j-1]:
                    dp[j] = pre  # 字符相同，无需操作
                else:
                    # 取插入、删除、替换操作的最小值
                    dp[j] = min(dp[j-1], dp[j], pre) + 1
                
                pre = temp  # 更新pre为当前格的旧值
        
        return dp[n]